import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class Solution {
    //JZ82 二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        sum=sum-root.val;
        if(root.left==null&&root.right==null&&sum==0){
            return true;
        }
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }
    //JZ79 判断是不是平衡二叉树
    class  TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    protected int getpath(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getpath(root.left);
        int right=getpath(root.right);
        return left>right?left+1:right+1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=getpath(root.left);
        int right=getpath(root.right);
        return Math.abs(left-right)<=1&&IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
}
    //JZ76 删除链表中重复的结点
    class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    public ListNode deleteDuplication(ListNode pHead) {
        HashMap<Integer,Integer> map=new HashMap<>();
        ListNode cur=pHead;
        while(cur!=null){
            if(map.containsKey(cur.val)){
                int val=map.get(cur.val);
                map.put(cur.val,val+1);

            }else{
                map.put(cur.val,1);
            }
            cur=cur.next;
        }
        ListNode newHead=new ListNode(0);
        newHead.next=pHead;
        cur=newHead;//避免头结点被删除掉
        while(cur.next!=null){
            if(map.get(cur.next.val)!=1){
                //删除该节点
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return newHead.next;
    }

    //JZ73 翻转单词序列
    public String ReverseSentence1(String str) {
        String [] arr=str.split(" ");
        Stack<String> s1=new Stack<>();
        for(String x:arr){
            s1.push(x);
        }
        StringBuffer ret=new StringBuffer();
        while(!s1.empty()){
            ret.append(" ");
            ret.append(s1.pop());
        }
        return ret.deleteCharAt(0).toString();
    }

   public String ReverseSentence(String str) {
       String [] arr=str.split(" ");
       StringBuffer ret=new StringBuffer();
       for(int i=arr.length-1;i>=0;i--){
           ret.append(" ");
           ret.append(arr[i]);
       }
       return ret.deleteCharAt(0).toString();
   }
}